package com.dzu.easy;

/**
 * @author ZhaoDong
 * @date 2022/11/2 11:03
 * @description 459. 重复的子字符串
 */
public class Test459 {

    public static void main(String[] args) {
        System.out.println(new Test459().repeatedSubstringPattern2("aa"));

    }

    // 7ms
    public static boolean repeatedSubstringPattern(String s) {

        int length = s.length();

        int start = 1;
        while (true) {
            if (length % start != 0) {
                start++;
                continue;
            }
            if (start >= length) {
                break;
            }
            String sub = s.substring(0, start);
            boolean flag = false;
            for (int i = 0; i < length; i += start) {
                String s1 = s.substring(i, i + start);
                if (!sub.equals(s1)) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                start++;
            } else {
                return true;
            }

        }
        return false;

    }

    // 那么如果将两个 ss 连在一起，并移除第一个和最后一个字符，那么得到的字符串一定包含 ss，即 ss 是它的一个子串。
    //    偷巧      return (s + s).indexOf(s, 1) != s.length();

    // kmp 14ms
    public boolean repeatedSubstringPattern2(String s) {

        return kmp(s + s, s);
    }


    public boolean kmp(String query, String pattern) {
        int n = query.length();
        int m = pattern.length();
        int[] next = new int[m];

        for (int i = 1, j = 0; i < m; ++i) {

            while (j != 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = next[j - 1];
            }
            if (pattern.charAt(j) == pattern.charAt(i)) {
                j++;
            }
            next[i] = j;
        }

        int match = 0;

        for (int i = 1; i < n - 1; i++) {

            while (match != 0 && pattern.charAt(match) != query.charAt(i)) {
                match = next[match - 1];
            }
            if (pattern.charAt(match) == query.charAt(i)) {
                match++;
                if (match == m) {
                    return true;
                }
            }
        }
        return false;
    }


}
